//
// Created by Semir on 2020/5/26.
//

#include <iostream>

using namespace std;

/*
    普通示例：
    1234
    个位为1：123*1+1    124
    十位为1：12*10+10   130
    百位为1：1*100+100  200
    千位为1：235        23

    分别根据每一位为1时考虑存在情况种类的个数 累加
    例如：pxq，x为此时考虑的数位，假设x位于s位（s为1/10/100/1000...）
    p为x左边代表的数值，q为x右边代表的数值
    则此时（x位为1）的数字的个数有：
    p*s+adder个
    adder根据x是否为0、1、大于1，分为3种情况
    if (x > 1) {
        sum += s;
    } else if (x == 1) {
        sum += s > 1 ? q + 1 : 1;
    } else {  //x == 0
        sum += s > 1 ? q : 0;
    }

    特殊考虑的用例
    1，9，10，11，10000
 */

int NumberOf1Between1AndN_Solution(int n) {
    int sum = 0;
    int s = 1;
    int ts = 10;
    int p = n;
    int x;
    int q;
    while (p != 0) {
        p = n / ts;
        x = (n / s) % 10;
        q = n % s;
        sum += p * s;
        if (x > 1) {
            sum += s;
        } else if (x == 1) {
            sum += s > 1 ? q + 1 : 1;
        } else {  //x == 0
            sum += s > 1 ? q : 0;
        }
        s = ts;
        ts *= 10;
    }
    return sum;
}

int main() {
    int res = NumberOf1Between1AndN_Solution(10000);
    cout << res << endl;
    return 0;
}